

In [ ]:

    
%%HTML
<style>
.container { width:100% }
</style>

Iterative Deepening A-Star Search

The function search takes four arguments to solve a search problem:

start is the start state of the search problem,
goalis the goal state, and
next_states is a function with signature $\texttt{next_states}:Q \rightarrow 2^Q$, where $Q$ is the set of states. For every state $s \in Q$, $\texttt{next_states}(s)$ is the set of states that can be reached from $s$ in one step.
heuristic is a function that takes two states as arguments.
It returns an estimate of the length of the shortest path between these states.

If successful, search returns a path from start to goal that is a solution of the search problem $$ \langle Q, \texttt{next_states}, \texttt{start}, \texttt{goal} \rangle. $$

The procedure search uses iterative deepening to compute a solution of the given search problem.



In [ ]:

    
def search(start, goal, next_states, heuristic):
    limit = heuristic(start, goal)
    while True:
        print(f'Trying to find a solution of length {limit}.')
        Path = dl_search([start], goal, next_states, limit, heuristic)
        if isinstance(Path, list):
            return Path
        limit = Path

The function dl_search tries to find a solution to the search problem $$ \langle Q, \texttt{next_states}, \texttt{start}, \texttt{goal} \rangle $$ that has a length of at most limit. It uses heuristic to cut short a search that would be unsuccessful. If it can not find a solution that satisfies the given limit, it returns a number that is a lower bound for the length of the solution. This lower bound will always be greater than limit and can be used in the next attempt to search for a solution.



In [ ]:

    
def dl_search(Path, goal, next_states, limit, heuristic):
    state    = Path[-1]
    distance = len(Path) - 1
    total    = distance + heuristic(state, goal)
    if total > limit:
        return total
    if state == goal:
        return Path
    smallest = float("Inf")  # infinity
    for ns in next_states(state):
        if ns not in Path:
            Solution = dl_search(Path + [ns], goal, next_states, limit, heuristic)
            if isinstance(Solution, list):
                return Solution
            smallest = min(smallest, Solution)
    return smallest

Solving the Sliding Puzzle



In [ ]:

    
%run Sliding-Puzzle.ipynb



In [ ]:

    
%%time
Path = search(start, goal, next_states, manhattan)
print(len(Path)-1)



In [ ]:

    
animation(Path)



In [ ]:

    
%%time
Path = search(start2, goal2, next_states, manhattan)
print(len(Path)-1)



In [ ]:

    
animation(Path)



In [ ]: